package 数据结构.树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-26
 */
public class JZ28对称的二叉树 {
    //递归
    public boolean isSymmetrical(TreeNode pRoot) {
        return  recursion(pRoot,pRoot);
    }

    public boolean recursion(TreeNode p1,TreeNode p2){
        if(p1 == null && p2 == null)
            return true;
        if(p1==null || p2==null || p1.val!= p2.val)
            return false;

        return recursion(p1.left,p2.right) && recursion(p1.right,p2.left);
    }

    //层次遍历
    public boolean isSymmetrical2(TreeNode pRoot) {
        if(pRoot == null)
            return true;
        Queue<TreeNode> q1 = new LinkedList();
        Queue<TreeNode> q2 = new LinkedList();
        q1.offer(pRoot.left);
        q2.offer(pRoot.right);
        while (!q1.isEmpty() && !q2.isEmpty()){
            TreeNode left = q1.poll();
            TreeNode right = q2.poll();

            if(left==null && right == null)
                continue;
            if(left==null || right==null || left.val!=right.val)
                return false;

            q1.offer(left.left);
            q1.offer(left.right);

            q2.offer(right.right);
            q2.offer(right.left);
        }
        return true;
    }
}
